﻿using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.Diagnostics.Contracts;
using System.Linq;
using System.Text;
using System.Xml.Serialization;

namespace MathService
{
    /// <summary>
    /// Полином степени N-1
    ///  a[0]+a[1]*x+a[2]*x^2+...+a[N-1]*x^(N-1)+a[N-1]*x^(N-1)
    /// где N - число элементов массива коэффициентов
    /// Нулевой элемент массива при нулевой степени члена полинома 
    /// </summary>
    [Serializable]
    //[DebuggerDisplay("Power = {Power}")]
    public class Polynom : ICloneable<Polynom>, IEquatable<Polynom>, IEnumerable<double>
    {
        /* -------------------------------------------------------------------------------------------- */



        /* -------------------------------------------------------------------------------------------- */

        /// <summary>Преобразовать массив корней полинома в коэффициенты прои степенях</summary>
        /// <param name="Root">Корни полинома</param>
        /// <returns>Коэффициенты при степенях</returns>
        public static double[] GetPowers(params double[] Root)
        {
            Contract.Requires(Root != null);
            Contract.Ensures(Contract.Result<double[]>() != null);
            Contract.Ensures(Contract.Result<double[]>().Length == Root.Length + 1);

            //Массив коэффициентов при степенях
            var lv_Power = new double[Root.Length + 1];

            //
            lv_Power[0] = 1;

            var lv_N = Root.Length;
            for(var n = 0; n < lv_N; n++)
            {
                var lv_POld = lv_Power[0];
                for(var i = 1; i < n + 2 && i < lv_N + 1; i++)
                {
                    var lv_PNew = lv_Power[i] - lv_POld * Root[n];
                    lv_POld = lv_Power[i];
                    lv_Power[i] = lv_PNew;
                }
            }
            return lv_Power;
        }

        /// <summary>Получить полином из корней полинома</summary>
        /// <param name="Root">Корни полинома</param>
        /// <returns>Полином с указанными корнями</returns>
        public static Polynom GetPolynom(params double[] Root)
        {
            Contract.Requires(Root != null);
            Contract.Ensures(Contract.Result<Polynom>() != null);

            return new Polynom(GetPowers(Root));
        }

        /* -------------------------------------------------------------------------------------------- */

        /// <summary>Коэффициенты при степенях</summary>
        private readonly double[] f_a;

        /* -------------------------------------------------------------------------------------------- */

        /// <summary>Коэффициенты при степенях</summary>
        [XmlArray(ElementName = "a")]
        public double[] Coefficients
        {
            [Pure, System.Diagnostics.DebuggerStepThrough]
            get
            {
                Contract.Ensures(Contract.Result<double[]>() != null);
                Contract.Ensures(Contract.Result<double[]>().Length > 0);
                return f_a;
            }
        }

        /// <summary>Степень полинома - число коэффициентов - 1</summary>
        public int Power
        {
            [Pure, DebuggerStepThrough]
            get
            {
                Contract.Ensures(Contract.Result<int>() >= 0);
                Contract.Ensures(Contract.Result<int>() == Length - 1);
                return f_a.Length - 1;
            }
        }

        /// <summary>Длина полинома - число коэффициентов</summary>
        public int Length
        {
            [Pure, DebuggerStepThrough]
            get
            {
                Contract.Ensures(Contract.Result<int>() > 0);
                Contract.Ensures(Contract.Result<int>() == Coefficients.Length);
                return Coefficients.Length;
            }
        }

        ///<summary>
        /// Коэффициент при степени <paramref name="n"/>, где <paramref name="n"/> принадлежит [0; <see cref="Power"/>]
        /// <see cref="Power"/> = <see cref="Length"/> - 1
        /// </summary>
        ///<param name="n">Степень a[0]+a[1]*x+a[2]*x^2+...<b>+a[<paramref name="n"/>]*x^<paramref name="n"/>+</b>...+a[N-1]*x^(N-1)+a[N-1]*x^(N-1)</param>
        public double this[int n]
        {
            [Pure, DebuggerStepThrough]
            get
            {
                Contract.Requires(n >= 0);
                Contract.Requires(n < Coefficients.Length);
                return f_a[n];
            }
            [DebuggerStepThrough]
            set
            {
                Contract.Requires(n >= 0);
                Contract.Requires(n < Coefficients.Length);
                f_a[n] = value;
            }
        }

        /* -------------------------------------------------------------------------------------------- */

        /// <summary>Полином степени N, нулевой элемент массива a[0] при младшей степени x^0</summary>
        /// <param name="a">a[0]+a[1]*x+a[2]*x^2+...+a[N-1]*x^(N-1)+a[N-1]*x^(N-1)</param>
        [Pure, DebuggerStepThrough]
        public Polynom(params double[] a)
        {
            Contract.Requires(a != null);
            Contract.Requires(a.Length > 0);
            Contract.Ensures(f_a != null);
            Contract.Ensures(f_a.Length > 0);
            Contract.Ensures(Power >= 0);
            f_a = (double[])a.Clone();
        }

        [Pure, DebuggerStepThrough]
        public Polynom(IEnumerable<double> a)
            : this(a.ToArray())
        {
            Contract.Requires(a != null);
            Contract.Requires(a.Any());
            Contract.Ensures(f_a != null);
            Contract.Ensures(f_a.Length > 0);
            Contract.Ensures(Power >= 0);
        }

        [Pure, DebuggerStepThrough]
        public Polynom(IEnumerable<int> a)
            : this(a.Cast<double>())
        {
            Contract.Requires(a != null);
            Contract.Requires(a.Any());
            Contract.Ensures(f_a != null);
            Contract.Ensures(f_a.Length > 0);
            Contract.Ensures(Power >= 0);
        }

        /* -------------------------------------------------------------------------------------------- */

        /// <summary>Получить значение полинома</summary>
        /// <param name="x">Переменная</param>
        /// <returns>Значение полинома в точке x</returns>
        [Pure, DebuggerStepThrough]
        public double Value(double x)
        {
            var N = f_a.Length;
            var lv_Result = f_a[N - 1];
            for(var i = 1; i < N; i++)
                lv_Result = lv_Result * x + f_a[(N - 1) - i];
            return lv_Result;
        }

        /* -------------------------------------------------------------------------------------------- */

        /// <summary>Явное приведение типов полинома к делегату функции преобразования double->double</summary>
        /// <param name="P">Полином</param>
        /// <returns>Делегат функции преобразования</returns>
        [Pure, DebuggerStepThrough]
        public static implicit operator Func<double, double>(Polynom P)
        {
            Contract.Ensures(Contract.Result<Func<double, double>>() != null);
            return P.Value;
        }

        /// <summary>Оператор сложения двух полиномов</summary>
        /// <param name="P">Первое слагаемое</param>
        /// <param name="Q">Второе слагаемое</param>
        /// <returns>Сумма полиномов</returns>
        [DebuggerStepThrough, Pure]
        public static Polynom operator +(Polynom P, Polynom Q)
        {
            Contract.Requires(P != null);
            Contract.Requires(Q != null);
            Contract.Ensures(Contract.Result<Polynom>() != null);
            Contract.Ensures(Contract.Result<Polynom>().Power == Math.Max(P.Power, Q.Power));

            var NP = P.Length;
            var NQ = Q.Length;
            int N;
            Polynom a, b;
            if(NP > NQ)
            {
                a = P.Clone();
                b = Q;
                N = NQ;
            }
            else
            {
                a = Q.Clone();
                b = P;
                N = NP;
            }

            for(var n = 0; n < N; n++)
                a.f_a[n] += b.f_a[n];

            return a;
        }

        /// <summary>
        /// Оператор отрицания полинома (изменяет знак всех коэффициентов на обратной). Эквивалентно домножению полинома на -1
        /// </summary>
        /// <param name="P">Отрицаемый полином</param>
        /// <returns>Полином Q = -P</returns>
        public static Polynom operator -(Polynom P)
        {
            Contract.Requires(P != null);
            Contract.Ensures(Contract.Result<Polynom>() != null);

            return new Polynom(new double[P.Length].Initialize(i => -P.f_a[i]));
        }

        /// <summary>Оператор вычетания полинома Q из полинома P</summary>
        /// <param name="P">Уменьшаемое</param>
        /// <param name="Q">Вычитаемое</param>
        /// <returns>Разность</returns>
        public static Polynom operator -(Polynom P, Polynom Q)
        {
            Contract.Requires(P != null);
            Contract.Requires(Q != null);
            Contract.Ensures(Contract.Result<Polynom>() != null);
            Contract.Ensures(Contract.Result<Polynom>().Power == Math.Max(P.Power, Q.Power));

            var NP = P.Length;
            var NQ = Q.Length;
            int N;
            Polynom a, b;
            if(NP > NQ)
            {
                a = P.Clone();
                b = -Q;
                N = NQ;
            }
            else
            {
                a = -Q.Clone();
                b = P;
                N = NP;
            }

            for(var n = 0; n < N; n++)
                a.f_a[n] += b.f_a[n];

            return a;
        }

        [NotImplemented]
        public static Polynom operator *(Polynom P, Polynom Q)
        {
            Contract.Requires(P != null);
            Contract.Requires(Q != null);
            Contract.Ensures(Contract.Result<Polynom>() != null);

            var p = P.f_a;
            var q = Q.f_a;
            var Np = p.Length;
            var Nq = q.Length;
            var Nx = Np * Nq;
            var x = new double[Nx];

            for(var i = 0; i < Nx; i++)
            {
                //var ip1 = i < Np ? 0 : i - Np;
                //var ip2 = i < Np ? i : Np - 1;

                //var iq1 = 0;

            }

            throw new NotImplementedException();
            //return new Polynom(x);
        }

        #region Implementation of ICloneable

        #endregion

        #region Implementation of IEquatable<Polynom>

        public bool Equals(Polynom other)
        {
            if(other == null) return false;

            var a = f_a;
            var b = other.f_a;
            var power = a.Length;

            if(power != b.Length) return false;
            for(var i = 0; i < power; i++)
                if(Math.Abs(f_a[i] - other.f_a[i]) > double.Epsilon)
                    return false;
            return true;
        }

        public Polynom Clone() { return new Polynom(f_a); }
        object ICloneable.Clone() { return Clone(); }

        [Pure, System.Diagnostics.DebuggerStepThrough]
        public override bool Equals(object obj) { return Equals(obj as Polynom); }

        #endregion

        [Pure, System.Diagnostics.DebuggerStepThrough]
        public override int GetHashCode()
        {
            return f_a.Select((i, a) => i.GetHashCode() ^ a.GetHashCode()).Aggregate(0x285da41, (S, s) => S ^ s);
        }

        /// <summary>Возвращает перечислитель, который осуществляет перебор элементов коллекции.</summary>
        /// <returns>
        /// Объект <see cref="T:System.Collections.IEnumerator"/>, который может использоваться для перебора элементов коллекции.
        /// </returns>
        /// <filterpriority>2</filterpriority>
        IEnumerator IEnumerable.GetEnumerator() { return ((IEnumerable<double>)this).GetEnumerator(); }

        /// <summary>Возвращает перечислитель, выполняющий перебор элементов в коллекции.</summary>
        /// <returns>
        /// Интерфейс <see cref="T:System.Collections.Generic.IEnumerator`1"/>, который может использоваться для перебора элементов коллекции.
        /// </returns>
        /// <filterpriority>1</filterpriority>
        IEnumerator<double> IEnumerable<double>.GetEnumerator() { return f_a.Cast<double>().GetEnumerator(); }

        public override string ToString()
        {
            return f_a.Aggregate(new StringBuilder(), (S, a, i) => S.AppendFormat("{0}{1}{2}",
                                        a < 0 || i == 0 ? "" : "+",
                                        a,
                                        i == 0 ? "" : string.Format("*x{0}", i == 1 ? "" : "^" + i))).ToString();
        }
    }
}
